package wwl.lsf;

import wwl.lsf.base.ListNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/5/24
 * @Description
 */
public class 删除链表的倒数第N个节点 {

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head);
            Deque<ListNode> stack = new LinkedList<ListNode>();
            ListNode cur = dummy;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
            for (int i = 0; i < n; ++i) {
                stack.pop();
            }
            ListNode prev = stack.peek();
            prev.next = prev.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    }


    public ListNode lianbiao(ListNode head, int n) {
        ListNode ya = new ListNode(0, head);

        Deque<ListNode> stack = new LinkedList();

        while (ya != null) {
            stack.push(ya);
            ya = ya.next;
        }
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        stack.peek().next = stack.peek().next.next;
        return ya.next;
    }

    public static ListNode tongbuweiyi(ListNode head, int n) {

        ListNode pre = new ListNode(0, head);
        ListNode first = pre;
        ListNode end = pre;

        while (n != 0) {
            first = first.next;
            n--;
        }
        while (first.next != null) {
            first = first.next;
            end = end.next;
        }
        end.next = end.next.next;
        return pre.next;
    }

    public static void main(String[] args) {

        ListNode listNode = new ListNode(2, null);
        ListNode head = new ListNode(1, listNode);
        tongbuweiyi(head, 1);


        LinkedList stack = new LinkedList<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.pop();
        stack.pop();
        Object peek = stack.peek();
        System.out.println("peek = " + peek);
        Object peek1 = stack.peek();
        System.out.println("peek1 = " + peek1);
    }
}
